home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / prog / graphics / plan_demo.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  7.8 KB  |  316 lines
  1. #include <math.h>
  2. #include <LEDA/graph.h>
  3. #include <LEDA/graph_alg.h>
  4. #include <LEDA/window.h>
  5. #include <LEDA/graph_edit.h>
  6.  
  7.  
  8. void draw_graph(const GRAPH<point,int>& G, window& W, bool numbering=false)
  9. { node v;
  10.   edge e;
  11.  
  12.   if (numbering)
  13.      { int i = 0;
  14.        forall_nodes(v,G) W.draw_int_node(G[v],i++,red);
  15.       }
  16.   else
  17.      forall_nodes(v,G) W.draw_filled_node(G[v],red);
  18.  
  19.   forall_edges(e,G)
  20.     W.draw_edge(G[source(e)],G[target(e)],blue);
  21. }
  22.  
  23.  
  24. main()
  25. {
  26.  
  27. panel P("LEDA Planarity Test Demo");
  28.  
  29. P.text_item("");
  30. P.text_item("This demo illustrates planarity testing and straight-line");
  31. P.text_item("embedding. You have two ways to construct a graph: either");
  32. P.text_item("interactively by using the LEDA graph editor or by calling");
  33. P.text_item("one of two graph generators. The first generator constructs");
  34. P.text_item("a random graph with a certain number of nodes and edges and");
  35. P.text_item("the second constructs a planar graph with a certain number");
  36. P.text_item("of nodes by intersecting random lines in the unit square");
  37. P.text_item("");
  38. P.text_item("The graph is displayed and then tested for planarity. If it");
  39. P.text_item("is planar a straight-line drawing is produced, otherwise, a");
  40. P.text_item("Kuratowski subgraph is highlighted.");
  41. P.button("continue");
  42.  
  43. P.open();
  44.  
  45. window W;
  46.  
  47. GRAPH<point,int>G;
  48. node v,w;
  49. edge e;
  50.  
  51. int n = 250;
  52. int m = 250;
  53. int embed = 0;
  54.  
  55.  
  56. const double pi= 3.14;
  57.  
  58. panel P1("PLANARITY TEST");
  59.  
  60. P1.text_item("The first slider asks for the number n of nodes and the second");
  61. P1.text_item("slider asks for the number m of edges. If you select the random");
  62. P1.text_item("button then a graph with n nodes and m edges is constructed, if");
  63. P1.text_item("you select the planar button then a set of random line segments");
  64. P1.text_item("is chosen and intersected to yield a planar graph with about n");
  65. P1.text_item("n nodes, and if you select the edit button the graph editor is");
  66. P1.text_item("called.");
  67. P1.text_item(" ");
  68.  
  69. P1.int_item("n = ",n,0,1000);
  70. P1.int_item("m = ",m,0,1000);
  71. P1.choice_item("embedding",embed,"FARY","SCHNYDER");
  72.  
  73. P1.button("random");
  74. P1.button("planar");
  75. P1.button("triang");
  76. P1.button("edit");
  77. P1.button("quit");
  78.  
  79. for(;;) 
  80. {
  81.   int inp = P1.open(W);
  82.  
  83.   if (inp == 4) break;   // quit button pressed
  84.  
  85.   W.init(0,1000,0);
  86.   W.set_node_width(4);
  87.  
  88.   switch(inp){
  89.  
  90.   case 0: { G.clear();
  91.             random_graph(G,n,m);
  92.             eliminate_parallel_edges(G);
  93.             
  94.             list<edge>Del= G.all_edges();
  95.             forall(e,Del) 
  96.                if (G.source(e)==G.target(e)) G.del_edge(e);
  97.   
  98.             float ang = 0;
  99.   
  100.             forall_nodes(v,G)
  101.             { G[v] = point(500+400*sin(ang),500+400*cos(ang));
  102.               ang += 2*pi/n;
  103.              }
  104.   
  105.              draw_graph(G,W);
  106.              break;
  107.            }
  108.   
  109.   case 1: { node_array<double> xcoord(G);
  110.             node_array<double> ycoord(G);
  111.             G.clear();
  112.             random_planar_graph(G,xcoord,ycoord,n);
  113.             forall_nodes(v,G)
  114.                G[v] = point(1000*xcoord[v], 900*ycoord[v]);
  115.   
  116.             draw_graph(G,W);
  117.             break;
  118.            }
  119.  
  120.   case 2: { node_array<double> xcoord(G);
  121.             node_array<double> ycoord(G);
  122.             G.clear();
  123.             triangulated_planar_graph(G,xcoord,ycoord,n);
  124.             forall_nodes(v,G)
  125.                G[v] = point(1000*xcoord[v], 900*ycoord[v]);
  126.   
  127.             draw_graph(G,W);
  128.             break;
  129.            }
  130.  
  131.   case 3: { W.set_node_width(12);
  132.             G.clear();
  133.             graph_edit(W,G,false);
  134.             break;
  135.            }
  136.   
  137.    }
  138.   
  139.   
  140.   
  141.   if (PLANAR(G,false))
  142.   { 
  143.     if(G.number_of_nodes()<4)
  144.         W.message("That's an insult: Every graph with |V| <= 4 is planar");
  145.     else
  146.       { W.message("G is planar. I compute a straight-line embedding ...");
  147.   
  148.         bool Gin_is_bidirected;
  149.   
  150.         node_array<int>nr(G);
  151.         edge_array<int>cost(G);
  152.         int cur_nr= 0;
  153.         int n = G.number_of_nodes();
  154.         node v;
  155.         edge e;
  156.         
  157.         forall_nodes(v,G)nr[v]= cur_nr++;
  158.         
  159.         forall_edges(e,G)cost[e]= ((nr[source(e)]<nr[target(e)])?
  160.         n*nr[source(e)]+nr[target(e)]:
  161.         n*nr[target(e)]+nr[source(e)]);
  162.         
  163.         G.sort_edges(cost);
  164.         
  165.         list<edge> L= G.all_edges();
  166.   
  167.         list<edge> n_edges;
  168.   
  169.         while(!L.empty())
  170.         { e= L.pop();
  171.   
  172.           if( ! L.empty() && source(e)==target(L.head())   
  173.                           && target(e)==source(L.head()))
  174.              L.pop();
  175.           else
  176.             { n_edges.append(G.new_edge(target(e),source(e)));
  177.               Gin_is_bidirected= false;
  178.              }
  179.          }
  180.   
  181.           make_biconnected_graph(G);
  182.   
  183.           PLANAR(G,true);
  184.   
  185.           node_array<int> xcoord(G),ycoord(G);
  186.  
  187.           float fx = 900.0/G.number_of_nodes();
  188.           float fy = 900.0/G.number_of_nodes();
  189.   
  190.           if (embed == 0)
  191.           { STRAIGHT_LINE_EMBEDDING(G,xcoord,ycoord);
  192.             fx = 900.0/(2*G.number_of_nodes());
  193.             fy = 900.0/G.number_of_nodes();
  194.             forall(e,n_edges) G.del_edge(e);
  195.             forall_nodes(v,G) G[v] = point(fx*xcoord[v]+30,fy*ycoord[v]+30);
  196.             W.clear();
  197.             if (inp == 0) 
  198.                draw_graph(G,W,true); // with node numbering
  199.             else
  200.                draw_graph(G,W);
  201.             }
  202.           else
  203.           { node a,b,c;
  204.             STRAIGHT_LINE_EMBEDDING2(G,a,b,c,xcoord,ycoord);
  205.             forall(e,n_edges) G.del_edge(e);
  206.  
  207.             int mx = 0;
  208.             forall_nodes(v,G) 
  209.             if (v != a && xcoord[v] > mx) mx = xcoord[v];
  210.      
  211.             mx += 2;
  212.      
  213.             list<node> A = G.adj_nodes(a);
  214.      
  215.             G.del_node(a);
  216.      
  217.             fx = 900.0/mx;
  218.      
  219.             W.clear();
  220.             forall_nodes(v,G) G[v] = point(fx*xcoord[v]+30,fy*ycoord[v]+30);
  221.      
  222.             draw_graph(G,W);
  223.      
  224.             a = G.new_node(point(fx*mx+30,500));
  225.      
  226.             W.draw_filled_node(G[a],red);
  227.      
  228.             node v;
  229.             forall(v,A)
  230.             { point p(G[a].xcoord(),G[v].ycoord());
  231.               W.draw_filled_node(p,black);
  232.               W.draw_edge(G[v],p,blue);
  233.               W.draw_edge(p,G[a],blue);
  234.              }
  235.           }
  236.  
  237.         }
  238.      }
  239.   else
  240.     { W.message("Graph is not planar. I compute the Kuratowski subgraph ...");
  241.  
  242.       list<edge> L;
  243.       edge e;
  244.  
  245.       PLANAR(G,L,false);
  246.  
  247.       edge_array<bool> marked(G,false);
  248.       node_array<int> side(G,0);
  249.  
  250.       forall(e,L) marked[e] = true;
  251.  
  252.       list<edge> el = G.all_edges();
  253.  
  254.       forall(e,el) 
  255.         if (!marked[e]) 
  256.           { //W.draw_edge(G[source(e)],G[target(e)],yellow);
  257.             G.del_edge(e);
  258.            }
  259.  
  260.       int lw = W.set_line_width(3);
  261.  
  262.       forall_edges(e,G) W.draw_edge(G[source(e)],G[target(e)]);
  263.  
  264.       node v;
  265.       forall_nodes(v,G) if (G.degree(v) == 3) break; 
  266.  
  267.       if (G.degree(v) == 3)
  268.         forall_inout_edges(e,v)
  269.         { marked[e] = false;
  270.           node w = G.opposite(v,e);
  271.           while (G.degree(w) == 2)
  272.           { edge x,y;
  273.             forall_inout_edges(x,w) 
  274.                if (marked[x]) y=x;
  275.              marked[y] = false;
  276.              w = G.opposite(w,y);
  277.            }
  278.           side[w] = 1;
  279.          }
  280.         
  281.  
  282.       int i = 1;
  283.       int j = 4;
  284.  
  285.       forall_nodes(v,G) 
  286.       { 
  287.         if (G.degree(v)==2) W.draw_filled_node(G[v],black);
  288.  
  289.         if (G.degree(v) > 2)
  290.         { int nw = W.set_node_width(10);
  291.           if (side[v]==0)
  292.              W.draw_int_node(G[v],i++,green);
  293.           else
  294.              if (W.mono())
  295.                 W.draw_int_node(G[v],j++,black);
  296.              else
  297.                 W.draw_int_node(G[v],j++,violet);
  298.  
  299.           W.set_node_width(nw);
  300.          }
  301.       }
  302.       W.set_line_width(lw);
  303.    }
  304.  
  305.    W.set_show_coordinates(false);
  306.    W.set_frame_label("click any button to continue");
  307.    W.read_mouse(); // wait for a click
  308.    W.reset_frame_label();
  309.    W.set_show_coordinates(true);
  310.  
  311.  } // for(;;)
  312.  
  313. return 0;
  314.  
  315. }
  316.